package chapter5_stack_and_linked;

import sun.awt.image.ImageWatched;
import sun.reflect.generics.tree.Tree;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @author yuh
 * @date 2018/4/12 10:43
 * @description 广度优先遍历 层序遍历
 */
public class WidthRow {

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }

        @Override
        public String toString() {
            return String.valueOf(val);
        }
    }

    public static List<LinkedList<TwoTuple<TreeNode, Integer>>> widthRow(TreeNode root) {
        List<LinkedList<TwoTuple<TreeNode, Integer>>> outer = new ArrayList<>();
        LinkedList<TwoTuple<TreeNode, Integer>> deque = new LinkedList<>();
        deque.addFirst(new TwoTuple<TreeNode, Integer>(root, 0));
        while (!deque.isEmpty()) {
            TwoTuple<TreeNode, Integer> tuple = deque.removeLast();
            int level = tuple.b;
            LinkedList<TwoTuple<TreeNode, Integer>> twoTuples = null;
            if (outer.size() <= level) {
                twoTuples = new LinkedList<>();
                outer.add(twoTuples);

            }else{
                twoTuples = outer.get(level);
            }
            twoTuples.addLast(tuple);
            if (tuple.a != null) {
                if (tuple.a.left != null) {
                    deque.addFirst(new TwoTuple<>(tuple.a.left, level + 1));
                }

                if (tuple.a.right != null) {
                    deque.addFirst(new TwoTuple<>(tuple.a.right, level + 1));
                }
            }
        }

        return outer;
    }

    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(1, new TreeNode(2, new TreeNode(4,null,null),null), new TreeNode(3, null, null));
        List<LinkedList<TwoTuple<TreeNode, Integer>>> linkedLists = widthRow(treeNode);
        System.out.println(linkedLists);
    }
}
